#ifndef __DYNAMICARRAY_H_
#define __DYNAMICARRAY_H_

#include <cstddef>
#include <limits.h>

namespace DARRAY
{
    using ElementType = void *;

    class DynamicArray
    {
    public:
        DynamicArray();
        DynamicArray(const DynamicArray &a);
        DynamicArray &operator=(const DynamicArray &a);
        ~DynamicArray();



        void SetFreeFunc(void (*Free)(void *))
        {
            this->Free = Free;
        }

        void SetPrintFunc(void (*print)(void *))
        {
            this->print = print;
        }

        void SetComprFunc(int (*compare)(void *, void *))
        {
            this->compare = compare;
        }

        void SetComprFunc(bool (*AllCompare)(void *, void *))
        {
            this->AllCompare = AllCompare;
        }

        // 插入
        // 尾插法:在size的位置插入
        void InsertTail(const ElementType &element);
        // 头插法： 在第一个位置插入
        void InsertHead(const ElementType &element);
        // 中间插入
        void InsertByIndex(const ElementType &element, size_t index);

        // 删除
        // 按位置删除
        void RemoveByIndex(size_t index);
        // 按值删除
        void RemoveByElement(const ElementType &element);

        // 查找
        // 按位置查找
        ElementType *FindByIndex(size_t index); // 返回指针 空和非空
        // 按值查找
        // 返回下标的集合
        DynamicArray FindByElement(const ElementType &element); // 返回数组

        // 修改
        void UpdateByIndex(size_t index, const ElementType &newValue);
        void UpdateByElement(const ElementType &element, const ElementType &newValue);

        ElementType &operator[](int index); // 查找和修改统一在一个接口里  不能判断非法值(只有指针可以判断非法值) 且不能判断越界

        // 排序算法
        void Sort();
        // 去重算法
        void Duplicate();
        // 合并:两个有序数列合并成一个新的有序数列
        DynamicArray Merge(const DynamicArray &a);
        // 取交集
        DynamicArray FdIntrSctn(const DynamicArray &a);
        // 取并集
        DynamicArray FindUnionSet(const DynamicArray &a);
        // 取补集
        DynamicArray FindDifference(const DynamicArray &a);

        // 判断两个数列是否相等
        bool operator==(const DynamicArray &a);

        // 二分法 没找到返回ULONMG_MAX
        size_t BinarySearch(const ElementType &element);
        // 判断一个数列是不是另一个数列的子数列
        bool Contains(const DynamicArray &a);
        // 判断一个数列是不是连续子序列
        bool ContnsContains(const DynamicArray &a);
        // 获取子序列
        DynamicArray SubSquence(size_t index, size_t len);

        void show();

    private:
        size_t partition(size_t start, size_t end);
        void FastSort(size_t start, size_t end, size_t CurDepth, size_t MaxDepth); // 一个最大的递归深度，防止爆栈
        void InsertSort(size_t start, size_t end);
        void ReSize(size_t capacity);
        ElementType *array;
        size_t capacity; // unsigned long
        size_t size;

        void (*Free)(void *);           // 释放对象的函数指针
        int (*compare)(void *, void *); // 比较大小的指针
        bool (*AllCompare)(void *, void *);
        void (*print)(void *); // 打印
    };
}

#endif
